package com.lry.basic.algorithm.common;

import java.util.Arrays;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/23
 */

//给你一个整数数组 nums 和一个正整数 k，请你判断是否可以把这个数组划分成一些由 k 个连续数字组成的集合。
//        如果可以，请返回 True；否则，返回 False。
//
//        示例 1：
//
//        输入：nums = [1,2,3,3,4,4,5,6], k = 4
//        输出：true
//        解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。
//
//        示例 2：
//
//        输入：nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
//        输出：true
//        解释：数组可以分成 [1,2,3] , [2,3,4] , [3,4,5] 和 [9,10,11]。
//
//        示例 3：
//
//        输入：nums = [3,3,2,2,1,1], k = 3
//        输出：true
//
//        示例 4：
//
//        输入：nums = [1,2,3,4], k = 3
//        输出：false
//        解释：数组不能分成几个大小为 3 的子数组。

public class IsPossibleDivide {
    public static void main(String[] args) {
        //1 2 2 3 3 3 4 4 5 9 10 11
        System.out.println(isPossibleDivide(new int[]{3,2,1,2,3,4,3,4,5,9,10,11},3));
    }
    public static boolean isPossibleDivide(int[] nums, int k) {
        Arrays.sort(nums);
        boolean[] flag = new boolean[nums.length];
        int i=1;
        int count = 1;
        int num = nums[0]+1;
        flag[0] = true;
        while(i<nums.length){
            if(nums[i]==num&&!flag[i]){
                count++;
                num = nums[i]+1;
                flag[i] = true;
            }
            i++;
            if(count==k){
                for (int j=0;j<flag.length;j++) {
                    if(!flag[j]){
                        count=1;
                        flag[j] = true;
                        i = j;
                        num = nums[j]+1;
                        break;
                    }
                }
            }
        }
        if(count!=k)
            return false;

        for (boolean f:flag) {
            if(!f){
                return false;
            }
        }

        return true;
    }
}
